package leetcode.leetcode215;

/**
 * @author czt
 * @version 1.0
 * @since 2024/12/25
 *
 * 查找第K大的元素
 *
 * 1.向小顶堆中放入前k个元素
 * 2.剩余元素
 *      若 <= 堆顶元素，则略过
 *      若 >= 堆顶元素，则替换堆顶元素
 * 3.这样小顶堆始终保留的是到目前为止，前k大的元素
 * 4.循环结束，堆顶元素即位第k大的元素
 */
public class Leetcode215 {

    public int findKthLargest(int[] nums, int k) {
        MinHeap heap = new MinHeap(k);
        for (int i = 0; i < k; i++) {
            heap.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > heap.peek()) {
                heap.replace(nums[i]);
            }
        }
        return heap.peek();
    }
}
